package com.yuufa.test.ex;

import com.yuufa.util.Tool;

public class Ex8 {
    
    public static void main(String[] args) {
        
        Queen.queen(1);
    }

    public static void ex8() {
        int n = 8;
        int[][] cost = initial(n);
        int[] dist = {0, Integer.MAX_VALUE, Integer.MAX_VALUE, Integer.MAX_VALUE, 
                      Integer.MAX_VALUE, Integer.MAX_VALUE, Integer.MAX_VALUE, 
                      Integer.MAX_VALUE, Integer.MAX_VALUE};
        int[] pred = new int[n + 1];
        int[] s = new int[n + 1];
        int v = 5;

        shortPath(v, cost, dist, pred, s, n);

        for (int i = 1; i <= n; i++) {
            System.out.print(dist[i] + ",");
        }
        System.out.println();
        for (int i = 1; i <= n; i++) {
            System.out.print(pred[i] + ",");
        }
    }

    public static int[][] initial(int n) {

        int[][] cost = new int[n + 1][n + 1];

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                cost[i][j] = Integer.MAX_VALUE;
            }
        }

        cost[2][1] = 300;
        cost[3][1] = 1000;
        cost[3][2] = 800;
        cost[4][3] = 1200;
        cost[5][4] = 1500;
        cost[5][6] = 250;
        cost[6][4] = 1000;
        cost[6][7] = 900;
        cost[6][8] = 1400;
        cost[7][8] = 1000;
        cost[8][1] = 1700;

        return cost;
    }

    public static int getShortestPathVertex(int[] s, int[] dist, int n) {

        int tmp = Integer.MAX_VALUE;
        int num = 0;

        for (int i = 1; i <= n; i++) {
            if (dist[i] != Integer.MAX_VALUE) {
                if (s[i] == 0) {
                    if (dist[i] < tmp) {
                        tmp = dist[i];
                        num = i;
                    }
                }
            }
        }

        return num;
    }

    public static void shortPath(int v, int[][] cost, int[] dist, int[] pred, int[] s, int n) {

        for (int i = 1; i <= n; i++) {
            if (cost[v][i] != Integer.MAX_VALUE) {
                dist[i] = cost[v][i];
                pred[i] = v;
            }
        }

        s[v] = 1;
        dist[v] = 0;
        pred[v] = 0;
        int num = 2;

        while (num <= n) {
            int vertex = getShortestPathVertex(s, dist, n);

            for (int i = 1; i <= n; i++) {
                if( cost[vertex][i] != Integer.MAX_VALUE ) {
                    if (s[i] == 0) {
                        if (dist[vertex] + cost[vertex][i] < dist[i]) {
                            dist[i] = dist[vertex] + cost[vertex][i];
                            pred[i] = vertex;
                        }
                    }
                }
            }

            s[vertex] = 1;
            num++;
        }

    }
}

class Queen {
    
    static int N = 8;
    static int[] q = new int[N+1];
    
    public static void queen(int i) {
        
        if( i == (N+1)) {
            Tool.print(q, 1, N);
        } else {
            for(int j=1;j<=N;j++) {
                q[i] = j;
                if( promising(i) ) {
                    queen(i+1);
                }
            }
        }
    }
    
    public static boolean promising(int i) {
        
        int k = 1;
        
        while(k < i) {
            if( q[i] == q[k] || (i-k) == Math.abs(q[i] - q[k]) ) {
                return false;
            }
            k++;
        }
        
        return true;
    }
}
